SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Iterative Stencil Loops</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Iterative Stencil Loops</span></span>

</h1>

</header>

<p><b>Iterative Stencil Loops</b> (ISLs) or <b>Stencil computations</b> are a class of numerical data processing solution<sup id="cite_ref-Roth_1-0" class="reference"><a href="#cite_note-Roth-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

which update <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array elements</a> according to some fixed pattern, called a stencil.<sup id="cite_ref-Sloot_2-0" class="reference"><a href="#cite_note-Sloot-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

They are most commonly found in <a href="Computer_simulation" title="Computer simulation">computer simulations</a>, e.g. for <a href="Computational_fluid_dynamics" title="Computational fluid dynamics">computational fluid dynamics</a> in the context of scientific and engineering applications.

Other notable examples include solving <a href="Partial_differential_equations" class="mw-redirect" title="Partial differential equations">partial differential equations</a>,<sup id="cite_ref-Roth_1-1" class="reference"><a href="#cite_note-Roth-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> the <a href="Jacobi_method" title="Jacobi method">Jacobi</a> kernel, the <a href="Gauss%E2%80%93Seidel_method" title="Gauss–Seidel method">Gauss–Seidel method</a>,<sup id="cite_ref-Sloot_2-1" class="reference"><a href="#cite_note-Sloot-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> <a href="Image_processing" class="mw-redirect" title="Image processing">image processing</a><sup id="cite_ref-Roth_1-2" class="reference"><a href="#cite_note-Roth-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> and <a href="Cellular_automaton" title="Cellular automaton">cellular automata</a>.<sup id="cite_ref-Fey_3-0" class="reference"><a href="#cite_note-Fey-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

The regular structure of the arrays sets stencil techniques apart from other modeling methods such as the <a href="Finite_element_method" title="Finite element method">Finite element method</a>. Most <a href="Finite_difference_method" title="Finite difference method">finite difference codes</a> which operate on regular grids can be formulated as ISLs.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>ISLs perform a sequence of sweeps (called timesteps) through a given array.<sup id="cite_ref-Sloot_2-2" class="reference"><a href="#cite_note-Sloot-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Generally this is a 2- or 3-dimensional regular grid.<sup id="cite_ref-Fey_3-1" class="reference"><a href="#cite_note-Fey-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> The elements of the arrays are often referred to as cells. In each timestep, all array elements are updated.<sup id="cite_ref-Sloot_2-3" class="reference"><a href="#cite_note-Sloot-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Using neighboring array elements in a fixed pattern (the stencil), each cell's new value is computed. In most cases boundary values are left unchanged, but in some cases (e.g. <a href="Lattice_Boltzmann_methods" title="Lattice Boltzmann methods">LBM codes</a>) those need to be adjusted during the computation as well. Since the stencil is the same for each element, the pattern of data accesses is repeated.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>More formally, we may define ISLs as a <a href="N-tuple" class="mw-redirect" title="N-tuple">5-tuple</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (I,S,S_{0},s,T)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (I,S,S_{0},s,T)}</annotation>

</semantics>

</math></span><img src="./d5cb3aca6e6c9ed353ec663f2e6d3ea7212d937e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.822ex; height:2.843ex;" alt="{\displaystyle (I,S,S_{0},s,T)}" loading="lazy"></span> with the following meaning:<sup id="cite_ref-Fey_3-2" class="reference"><a href="#cite_note-Fey-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I=\prod _{i=1}^{k}[0,\ldots ,n_{i}]}</annotation>

</semantics>

</math></span><img src="./19d99502dae6ee35878eb2120c3c39e47b0a388d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.068ex; height:7.343ex;" alt="{\displaystyle I=\prod _{i=1}^{k}[0,\ldots ,n_{i}]}" loading="lazy"></span> is the index set. It defines the topology of the array.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> is the (not necessarily finite) set of states, one of which each cell may take on on any given timestep.</li>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{0}\colon \mathbb {Z} ^{k}\to S}</annotation>

</semantics>

</math></span><img src="./2900256cdd481ecdf3aca2cb2dfd4e485185b8d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.265ex; height:3.009ex;" alt="{\displaystyle S_{0}\colon \mathbb {Z} ^{k}\to S}" loading="lazy"></span> defines the initial state of the system at time 0.</li>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\in \prod _{i=1}^{l}\mathbb {Z} ^{k}}</annotation>

</semantics>

</math></span><img src="./fa853fff1bb04e872386bd16621e601926291cb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:9.927ex; height:7.343ex;" alt="{\displaystyle s\in \prod _{i=1}^{l}\mathbb {Z} ^{k}}" loading="lazy"></span> is the stencil itself and describes the actual shape of the neighborhood. There are <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span> elements in the stencil.</li>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\colon S^{l}\to S}</annotation>

</semantics>

</math></span><img src="./4b4127f34fece67024b1f63ba77a57f97adb3383.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.028ex; height:2.676ex;" alt="{\displaystyle T\colon S^{l}\to S}" loading="lazy"></span> is the transition function which is used to determine a cell's new state, depending on its neighbors.</li></ul>

<p>Since <i>I</i> is a <i>k</i>-dimensional integer interval, the array will always have the topology of a finite regular grid. The array is also called simulation space and individual cells are identified by their index <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in I}</annotation>

</semantics>

</math></span><img src="./35a5b9f415c090a0c29b6b3452805563bfd3eb9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.019ex; height:2.176ex;" alt="{\displaystyle c\in I}" loading="lazy"></span>. The stencil is an ordered set of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span> relative coordinates. We can now obtain for each cell <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> the tuple of its neighbors indices <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I_{c}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{c}}</annotation>

</semantics>

</math></span><img src="./7463de5fff5fee0c540ac1d8cd1aca43f4852c65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.967ex; height:2.509ex;" alt="{\displaystyle I_{c}}" loading="lazy"></span>

</p>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{c}=\{j\mid \exists x\in s:j=c+x\}\,}</annotation>

</semantics>

</math></span><img src="./e9626d83999471da5de06f13a832716028922829.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.397ex; height:2.843ex;" alt="{\displaystyle I_{c}=\{j\mid \exists x\in s:j=c+x\}\,}" loading="lazy"></span></dd></dl>

<p>Their states are given by mapping the tuple <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I_{c}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{c}}</annotation>

</semantics>

</math></span><img src="./7463de5fff5fee0c540ac1d8cd1aca43f4852c65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.967ex; height:2.509ex;" alt="{\displaystyle I_{c}}" loading="lazy"></span> to the corresponding tuple of states <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{i}(c)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{i}(c)}</annotation>

</semantics>

</math></span><img src="./67293158e946cbbf188e823087149f4fb84fa4fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.482ex; height:2.843ex;" alt="{\displaystyle N_{i}(c)}" loading="lazy"></span>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{i}\colon I\to S^{l}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{i}\colon I\to S^{l}}</annotation>

</semantics>

</math></span><img src="./38c4e75ea150d594637cc8cc678adf1b12069432.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.73ex; height:3.009ex;" alt="{\displaystyle N_{i}\colon I\to S^{l}}" loading="lazy"></span> is defined as follows:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{i}(c)=(s_{1},\ldots ,s_{l}){\text{ with }}s_{j}=S_{i}(I_{c}(j))\,}</annotation>

</semantics>

</math></span><img src="./292e4f470fa69e93872db345d571733dc85d1191.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:39.463ex; height:3.009ex;" alt="{\displaystyle N_{i}(c)=(s_{1},\ldots ,s_{l}){\text{ with }}s_{j}=S_{i}(I_{c}(j))\,}" loading="lazy"></span></dd></dl>

<p>This is all we need to define the system's state for the following time steps <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{i+1}\colon \mathbb {Z} ^{k}\to S}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i+1}\colon \mathbb {Z} ^{k}\to S}</annotation>

</semantics>

</math></span><img src="./ac6800b077a98654571fd05f8747bfd680dacba3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.111ex; height:3.009ex;" alt="{\displaystyle S_{i+1}\colon \mathbb {Z} ^{k}\to S}" loading="lazy"></span> with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./e64c8c5906eb3eb9d7a8b1ed1e31de4e5fc6c632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.321ex; height:2.176ex;" alt="{\displaystyle i\in \mathbb {N} }" loading="lazy"></span>:

</p>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i+1}(c)={\begin{cases}T(N_{i}(c)),&c\in I\\S_{i}(c),&c\in \mathbb {Z} ^{k}\setminus I\end{cases}}}</annotation>

</semantics>

</math></span><img src="./0768b1882c9ed4329790940fd4c1ac063ffe3b35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:34.484ex; height:6.176ex;" alt="{\displaystyle S_{i+1}(c)={\begin{cases}T(N_{i}(c)),&c\in I\\S_{i}(c),&c\in \mathbb {Z} ^{k}\setminus I\end{cases}}}" loading="lazy"></span></dd></dl>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i}}</annotation>

</semantics>

</math></span><img src="./de6e810a93f67802ecb603ee0e3324005c6e583e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.225ex; height:2.509ex;" alt="{\displaystyle S_{i}}" loading="lazy"></span> is defined on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} ^{k}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} ^{k}}</annotation>

</semantics>

</math></span><img src="./2804394ff2f7291056f4c050dc1b32809e755bdb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.639ex; height:2.676ex;" alt="{\displaystyle \mathbb {Z} ^{k}}" loading="lazy"></span> and not just on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I}</annotation>

</semantics>

</math></span><img src="./535ea7fc4134a31cbe2251d9d3511374bc41be9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.172ex; height:2.176ex;" alt="{\displaystyle I}" loading="lazy"></span> since the boundary conditions need to be set, too. Sometimes the elements of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I_{c}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{c}}</annotation>

</semantics>

</math></span><img src="./7463de5fff5fee0c540ac1d8cd1aca43f4852c65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.967ex; height:2.509ex;" alt="{\displaystyle I_{c}}" loading="lazy"></span> may be defined by a vector addition modulo the simulation space's dimension to realize toroidal topologies:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{c}=\{j\mid \exists x\in s:j=((c+x)\mod (n_{1},\ldots ,n_{k}))\}}</annotation>

</semantics>

</math></span><img src="./11ca6be391e9d88e06ede945bb2bc0081798612f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:51.423ex; height:2.843ex;" alt="{\displaystyle I_{c}=\{j\mid \exists x\in s:j=((c+x)\mod (n_{1},\ldots ,n_{k}))\}}" loading="lazy"></span></dd></dl>

<p>This may be useful for implementing <a href="Periodic_boundary_conditions" title="Periodic boundary conditions">periodic boundary conditions</a>, which simplifies certain physical models.

</p>

<div class="mw-heading mw-heading3"><h3 id="Example:_2D_Jacobi_iteration">Example: 2D Jacobi iteration</h3></div>

<p>To illustrate the formal definition, we'll have a look at how a two dimensional <a href="Jacobi_method" title="Jacobi method">Jacobi</a> iteration can be defined. The update function computes the arithmetic mean of a cell's four neighbors. In this case we set off with an initial solution of 0. The left and right boundary are fixed at 1, while the upper and lower boundaries are set to 0. After a sufficient number of iterations, the system converges against a saddle-shape.

</p>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}I&=[0,\ldots ,99]^{2}\\S&=\mathbb {R} \\S_{0}&:\mathbb {Z} ^{2}\to \mathbb {R} \\S_{0}((x,y))&={\begin{cases}1,&x<0\\0,&0\leq x<100\\1,&x\geq 100\end{cases}}\\s&=((0,-1),(-1,0),(1,0),(0,1))\\T&\colon \mathbb {R} ^{4}\to \mathbb {R} \\T((x_{1},x_{2},x_{3},x_{4}))&=0.25\cdot (x_{1}+x_{2}+x_{3}+x_{4})\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./3a98144c40a2769f290b0d8dfbd31d20ecaa062e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -13.171ex; width:50.942ex; height:27.509ex;" alt="{\displaystyle {\begin{aligned}I&=[0,\ldots ,99]^{2}\\S&=\mathbb {R} \\S_{0}&:\mathbb {Z} ^{2}\to \mathbb {R} \\S_{0}((x,y))&={\begin{cases}1,&x<0\\0,&0\leq x<100\\1,&x\geq 100\end{cases}}\\s&=((0,-1),(-1,0),(1,0),(0,1))\\T&\colon \mathbb {R} ^{4}\to \mathbb {R} \\T((x_{1},x_{2},x_{3},x_{4}))&=0.25\cdot (x_{1}+x_{2}+x_{3}+x_{4})\end{aligned}}}" loading="lazy"></span></dd></dl>

/* start https://en.wikipedia.org/ */

.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="thumb tmulti tnone center"><div class="thumbinner multiimageinner" style="width:669px;max-width:669px"><div class="trow"><div class="tsingle" style="margin-right:10px;width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{0}}</annotation>

</semantics>

</math></span><img src="./ebe0ac45a38c4437bd2689a14ec434cd499e7e49.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{0}}" loading="lazy"></span></div></div><div class="tsingle" style="margin-right:10px;width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{200}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{200}}</annotation>

</semantics>

</math></span><img src="./e8524bf8c8531ddbf919c052b37c5c09f71259a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.123ex; height:2.509ex;" alt="{\displaystyle S_{200}}" loading="lazy"></span></div></div><div class="tsingle" style="margin-right:10px;width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{400}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{400}}</annotation>

</semantics>

</math></span><img src="./ab37b5ed0c083c4b48c91bec6da78a0363bd232e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.123ex; height:2.509ex;" alt="{\displaystyle S_{400}}" loading="lazy"></span></div></div><div class="tsingle" style="margin-right:10px;width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{600}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{600}}</annotation>

</semantics>

</math></span><img src="./2a9cf9c598bb19a5c712e0c4413ea08d91e95c3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.123ex; height:2.509ex;" alt="{\displaystyle S_{600}}" loading="lazy"></span></div></div><div class="tsingle" style="margin-right:10px;width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{800}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{800}}</annotation>

</semantics>

</math></span><img src="./0a19030f7dccb18d66814e58a511d991bb0ad216.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.123ex; height:2.509ex;" alt="{\displaystyle S_{800}}" loading="lazy"></span></div></div><div class="tsingle" style="width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1000}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1000}}</annotation>

</semantics>

</math></span><img src="./260773e42b1b395628b56db305a50a760686df30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.945ex; height:2.509ex;" alt="{\displaystyle S_{1000}}" loading="lazy"></span></div></div></div><div class="trow" style="display:flex"><div class="thumbcaption">2D Jacobi Iteration on a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 100^{2}}</annotation>

</semantics>

</math></span><img src="./58b3a479370b385bb11d28e64bb519b585618779.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.542ex; height:2.676ex;" alt="{\displaystyle 100^{2}}" loading="lazy"></span> Array</div></div></div></div>

<div class="mw-heading mw-heading2"><h2 id="Stencils">Stencils</h2></div>

<p>The shape of the neighborhood used during the updates depends on the application itself. The most common stencils are the 2D or 3D versions of the <a href="Von_Neumann_neighborhood" title="Von Neumann neighborhood">von Neumann neighborhood</a> and <a href="Moore_neighborhood" title="Moore neighborhood">Moore neighborhood</a>. The example above uses a 2D von Neumann stencil while LBM codes generally use its 3D variant. <a href="Conway's_Game_of_Life" title="Conway's Game of Life">Conway's Game of Life</a> uses the 2D Moore neighborhood. That said, other stencils such as a 25-point stencil for seismic wave propagation<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> can be found, too.

</p>

<div class="thumb tmulti tnone center"><div class="thumbinner multiimageinner" style="width:416px;max-width:416px"><div class="trow"><div class="tsingle" style="width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">9-point 2D stencil</div></div><div class="tsingle" style="width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">5-point 2D stencil</div></div><div class="tsingle" style="width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">7-point 3D stencil</div></div><div class="tsingle" style="width:102px;max-width:102px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">25-point 3D stencil</div></div></div><div class="trow" style="display:flex"><div class="thumbcaption">A selection of stencils used in various scientific applications.</div></div></div></div>

<div class="mw-heading mw-heading2"><h2 id="Implementation_issues">Implementation issues</h2></div>

<p>Many simulation codes may be formulated naturally as ISLs. Since computing time and memory consumption grow linearly with the number of array elements, parallel implementations of ISLs are of paramount importance to research.<sup id="cite_ref-Datta_6-0" class="reference"><a href="#cite_note-Datta-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

This is challenging since the computations are tightly coupled (because of the cell updates depending on neighboring cells) and most ISLs are <a href="Arithmetic_intensity" class="mw-redirect" title="Arithmetic intensity">memory bound</a> (i.e. the ratio of memory accesses to calculations is high).<sup id="cite_ref-Wellein_7-0" class="reference"><a href="#cite_note-Wellein-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

Virtually all current parallel architectures have been explored for executing ISLs efficiently;<sup id="cite_ref-datta2_8-0" class="reference"><a href="#cite_note-datta2-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

at the moment <a href="GPGPU" class="mw-redirect" title="GPGPU">GPGPUs</a> have proven to be most efficient.<sup id="cite_ref-schaefer_9-0" class="reference"><a href="#cite_note-schaefer-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Libraries">Libraries</h2></div>

<p>Due to both the importance of ISLs to <a href="Computer_simulation" title="Computer simulation">computer simulations</a> and their high computational requirements, there are a number of efforts which aim at creating reusable libraries to support scientists in performing stencil-based computations. The libraries are mostly concerned with the parallelization, but may also tackle other challenges, such as IO, <a href="Computational_steering" title="Computational steering">steering</a> and <a href="Application_checkpointing" title="Application checkpointing">checkpointing</a>. They may be classified by their APIs.

</p>

<div class="mw-heading mw-heading3"><h3 id="Patch-based_libraries">Patch-based libraries</h3></div>

<p>This is a traditional design. The library manages a set of <i>n</i>-dimensional scalar arrays, which the user program may access to perform updates. The library handles the synchronization of the boundaries (dubbed ghost zone or halo). The advantage of this interface is that the user program may loop over the arrays, which makes it easy to integrate legacy code <sup id="cite_ref-walberla_10-0" class="reference"><a href="#cite_note-walberla-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

. The disadvantage is that the library can not handle cache blocking (as this has to be done within the loops<sup id="cite_ref-35dblocking_11-0" class="reference"><a href="#cite_note-35dblocking-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>)

or wrapping of the API-calls for accelerators (e.g. via CUDA or OpenCL). Implementations include <a rel="nofollow" class="external text" href="http://cactuscode.org/">Cactus</a>, a physics problem solving environment, and <a rel="nofollow" class="external text" href="http://walberla.net/">waLBerla</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Cell-based_libraries">Cell-based libraries</h3></div>

<p>These libraries move the interface to updating single simulation cells: only the current cell and its neighbors are exposed, e.g. via getter/setter methods. The advantage of this approach is that the library can control tightly which cells are updated in which order, which is useful not only to implement cache blocking,<sup id="cite_ref-schaefer_9-1" class="reference"><a href="#cite_note-schaefer-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> but also to run the same code on multi-core systems and GPUs.<sup id="cite_ref-physis_12-0" class="reference"><a href="#cite_note-physis-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> This approach requires the user to recompile the source code together with the library. Otherwise a function call for every cell update would be required, which would seriously impair performance. This is only feasible with techniques such as <a href="Template_(programming)" class="mw-redirect" title="Template (programming)">class templates</a> or <a href="Metaprogramming" title="Metaprogramming">metaprogramming</a>, which is also the reason why this design is only found in newer libraries. Examples are <a rel="nofollow" class="external text" href="https://github.com/naoyam/physis">Physis</a> and <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220625193837/https://libgeodecomp.org/">LibGeoDecomp</a>.

</p>

<ul><li><a href="Advanced_Simulation_Library" title="Advanced Simulation Library">Advanced Simulation Library</a></li>

<li><a href="Finite_difference_method" title="Finite difference method">Finite difference method</a></li>

<li><a href="Computer_simulation" title="Computer simulation">Computer simulation</a></li>

<li><a href="Five-point_stencil" title="Five-point stencil">Five-point stencil</a></li>

<li><a href="Compact_stencil" title="Compact stencil">Compact stencil</a></li>

<li><a href="Non-compact_stencil" title="Non-compact stencil">Non-compact stencil</a></li>

<li><a href="Stencil_jumping" title="Stencil jumping">Stencil jumping</a></li>

<li><a href="Stencil_(numerical_analysis)" title="Stencil (numerical analysis)">Stencil (numerical analysis)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 33em;">

Roth, Gerald et al. (1997)

Proceedings of SC'97: High Performance Networking and Computing.

<i><a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.1505">Compiling Stencils in High Performance Fortran.</a></i></span>

</li>

Sloot, Peter M.A. et al. (May 28, 2002)

<i><a rel="nofollow" class="external text" href="https://books.google.com/books?id=qVcLw1UAFUsC&dq=stencil+array&pg=PA843">Computational Science – ICCS 2002: International Conference, Amsterdam, the Netherlands, April 21–24, 2002. Proceedings, Part I.</a></i>

Page 843. Publisher: Springer. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-43591-3</bdi>.</span>

</li>

Fey, Dietmar et al. (2010)

<i><a rel="nofollow" class="external text" href="https://books.google.com/books?id=RJRZJHVyQ4EC&dq=fey+grid&pg=PA51">Grid-Computing: Eine Basistechnologie für Computational Science</a></i>.

Page 439. Publisher: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-79746-7</bdi></span>

</li>

Yang, Laurence T.; Guo, Minyi. (August 12, 2005)

<i><a rel="nofollow" class="external text" href="https://books.google.com/books?id=qA4DbnFB2XcC&dq=Stencil+codes&pg=PA221">High-Performance Computing : Paradigm and Infrastructure.</a></i>

Page 221. Publisher: Wiley-Interscience. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-471-65471-X</bdi></span>

</li>

Micikevicius, Paulius et al. (2009)

<i><a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1513905">3D finite difference computation on GPUs using CUDA</a></i>

Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units

</li>

<li id="cite_note-Datta-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Datta_6-0">^</a></b></span> <span class="reference-text">Datta, Kaushik (2009)

<i><a rel="nofollow" class="external text" href="http://www.cs.berkeley.edu/~kdatta/pubs/EECS-2009-177.pdf">Auto-tuning Stencil Codes for Cache-Based Multicore Platforms</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20121008024435/http://www.cs.berkeley.edu/~kdatta/pubs/EECS-2009-177.pdf">Archived</a> 2012-10-08 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></i>,

Ph.D. Thesis</span>

</li>

Wellein, G et al. (2009)

<i><a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/5254211/;jsessionid=82537E9317BC47E65AACEF3F7823B703?arnumber=5254211">Efficient temporal blocking for stencil computations by multicore-aware wavefront parallelization</a></i>,

33rd Annual IEEE International Computer Software and Applications Conference, COMPSAC 2009</span>

</li>

Datta, Kaushik et al. (2008)

<i><a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1413375">Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures</a>,</i>

SC '08 Proceedings of the 2008 ACM/IEEE conference on Supercomputing</span>

</li>

Schäfer, Andreas and Fey, Dietmar (2011)

<i><a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S1877050911002791">High Performance Stencil Code Algorithms for GPGPUs</a></i>,

Proceedings of the International Conference on Computational Science, ICCS 2011</span>

</li>

S. Donath, J. Götz, C. Feichtinger, K. Iglberger and U. Rüde (2010)

<i><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-13872-0_3">waLBerla: Optimization for Itanium-based Systems with Thousands of Processors</a></i>,

High Performance Computing in Science and Engineering, Garching/Munich 2009</span>

</li>

Nguyen, Anthony et al. (2010)

<i><a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=1884658">3.5-D Blocking Optimization for Stencil Computations on Modern CPUs and GPUs</a></i>,

SC '10 Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis</span>

</li>

Naoya Maruyama, Tatsuo Nomura, Kento Sato, and Satoshi Matsuoka (2011)

<i>Physis: An Implicitly Parallel Programming Model for Stencil Computations on Large-Scale GPU-Accelerated Supercomputers</i>,

SC '11 Proceedings of the 2011 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis</span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://github.com/naoyam/physis">Physis</a></li>

<li><a rel="nofollow" class="external text" href="http://www.libgeodecomp.org">LibGeoDecomp</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220625193837/https://libgeodecomp.org/">Archived</a> 2022-06-25 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>

<li><a rel="nofollow" class="external text" href="http://walberla.net">waLBerla</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-02" href="https://en.wikipedia.org/wiki/?title=Iterative_Stencil_Loops&oldid=1278452278">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>